package com.leetcode.optimize;

import org.testng.annotations.Test;

public class FlattenBinaryTree {
	public void flatten(TreeNode root) {
		if (root == null) return;
		flat(root);
    }
	
	private TreeNode flat(TreeNode node) {
		if (node == null) return null;
		
		TreeNode leftTail = flat(node.left);
		TreeNode rightTail = flat(node.right);
		
		if (node.left != null) {
			leftTail.left = null;
			leftTail.right = node.right;
			node.right = node.left;
		}
		node.left = null;
		
		if (rightTail != null) return rightTail;
		return leftTail != null ? leftTail : node;
	}
	
	private class TreeNode {
		TreeNode left;
		TreeNode right;
		int val;
		public TreeNode(int val) {
			this.val = val;
		}
	}
	
	@Test
	public void test1() {
		TreeNode root = new TreeNode(1);
		TreeNode left = new TreeNode(2);
		TreeNode right = new TreeNode(3);
		root.left = left;
		root.right = right;
		flatten(root);
		System.out.println();
	}
}
